#include "MatrixGraph.h"
#include <iostream>
#include <assert.h>
#include <stdlib.h>

void discreteTest();
void simpleTest();
void algorithmsTest();


int main() {
  
  simpleTest();
  algorithmsTest();

  MatrixGraph * g = new MatrixGraph();
  g->insertVertex("a");
  g->insertVertex("b");
  g->insertVertex("c");
  g->insertVertex("d");
  g->insertEdge("a", "b", 10);
  g->insertEdge("b", "c", 20);
  g->insertEdge("a", "c", 100);

  

  delete g;


  /*
  MatrixGraph * g = new MatrixGraph();
  g->consistencyCheck();

  Vertex * a = g->insertVertex("a");
  Vertex * b = g->insertVertex("b");
  Vertex * c = g->insertVertex("c");

  g->consistencyCheck();
  assert (g->getNeighbors(a)->size() == 0);
  assert (g->getNeighbors(b)->size() == 0);
  assert (g->getNeighbors(c)->size() == 0);

  g->insertEdge(a, b);
  g->insertEdge(a, c);

  g->consistencyCheck();
  
  assert (g->getOutgoingEdges(a)->size() == 2);
  assert (g->getIncomingEdges(b)->size() == 1);
  
  delete g;
  */

  discreteTest();

}


void algorithmsTest() {

  /* Graph drawing:

a <<<<<<<<<<   d
  \              \
   V           |  \
   c           |    \
               V     V
               b <-> e


  */

  MatrixGraph * g = new MatrixGraph();
  g->insertEdge("a", "c");
  g->insertEdge("d", "a");
  g->insertEdge("d", "b");
  g->insertEdge("d", "e");
  g->insertEdge("b", "e");
  g->insertEdge("e", "b");

  unordered_map<string, string> * bfs = g->BFS("d");
  assert(bfs->find("d")->second == "Origin");
  assert(bfs->find("a")->second == "d");
  assert(bfs->find("b")->second == "d");
  assert(bfs->find("c")->second == "a");
  assert(bfs->find("e")->second == "d");
  delete bfs;

  bfs = g->BFS("a");
  assert(bfs->find("a")->second == "Origin");
  assert(bfs->find("b")->second == "None");
  assert(bfs->find("c")->second == "a");
  assert(bfs->find("e")->second == "None");
  assert(bfs->find("e")->second == "None");
  delete bfs;

  delete g;

  /*  A graph in the shape of a C

      a >>>>>> b
      |
      V
      V
      c >>>>>> d
  */
  g = new MatrixGraph();
  g->insertEdge("a", "b");
  g->insertEdge("a", "c");
  g->insertEdge("c", "d");

  unordered_map<string, string> * dfs = g->DFS("a");
  
  assert(dfs->find("a")->second == "Origin");
  assert(dfs->find("b")->second == "a");
  assert(dfs->find("c")->second == "a");
  assert(dfs->find("d")->second == "c");

  delete dfs;
  
  g->insertEdge("d", "b");
  vector < string > * top = g->TopologicalOrdering();
  assert( top->at(0) == "a" );
  assert( top->at(1) == "c" );
  assert( top->at(2) == "d" );
  assert( top->at(3) == "b" );
  delete top;

  delete g;
  /* A graph in a triangular shape 
        
         1
     A  ---  B
      \     /
  10   \   /  5
         C 
  */

  g = new MatrixGraph();
  g->insertEdge("a", "b", 1);
  g->insertEdge("b", "a", 1);
  g->insertEdge("a", "c", 10);
  g->insertEdge("c", "a", 10);
  g->insertEdge("c", "b", 5);
  g->insertEdge("b", "c", 5);

  unordered_map<string, string> * dijkstra = g->Dijkstra("a");
  assert(dijkstra->find("b")->second == "a");
  assert(dijkstra->find("c")->second == "b");
  delete dijkstra;
  
  g->removeEdge("b", "a");
  g->removeEdge("c", "b");
  g->removeEdge("c", "a");
  g->insertEdge("b", "d", 15);
  Edge * ab = g->getEdge("a", "b");
  Edge * ac = g->getEdge("a", "c");
  Edge * bc = g->getEdge("b", "c");
  Edge * bd = g->getEdge("b", "d");
  vector < Edge * > * kruskal = g->KruskalMST();
  assert( kruskal->size() == 3 );
  
  assert( kruskal->at(0) == ab or kruskal->at(0) == bc or kruskal->at(0) == bd );
  assert( kruskal->at(1) == ab or kruskal->at(1) == bc or kruskal->at(1) == bd ); 
  assert( kruskal->at(2) == ab or kruskal->at(2) == bc or kruskal->at(2) == bd );

  assert( kruskal->at(0) != kruskal->at(1) );
  assert( kruskal->at(0) != kruskal->at(2) );
  assert( kruskal->at(1) != kruskal->at(2) );

  assert( kruskal->at(0) != ac and kruskal->at(1) != ac and kruskal->at(2) != ac);
  delete kruskal;


  vector < Edge * > * prim = g->PrimMST("a");
  assert( prim->size() == 3 );
  
  assert( prim->at(0) == ab or prim->at(0) == bc or prim->at(0) == bd );
  assert( prim->at(1) == ab or prim->at(1) == bc or prim->at(1) == bd ); 
  assert( prim->at(2) == ab or prim->at(2) == bc or prim->at(2) == bd );

  assert( prim->at(0) != prim->at(1) );
  assert( prim->at(0) != prim->at(2) );
  assert( prim->at(1) != prim->at(2) );

  assert( prim->at(0) != ac and prim->at(1) != ac and prim->at(2) != ac);
  delete prim;



  delete g;
  

  g = new MatrixGraph();
  unordered_map<string, int > * distances = new unordered_map < string, int >;
  unordered_map<string, string> * priors = new unordered_map < string, string >;
  g->insertEdge("a", "b", -1);
  g->insertEdge("b", "c", -2);
  g->insertEdge("c", "a", 4);

  int nc = g->BellmanFord( "a", distances, priors );
  
  assert( distances->find("a")->second == 0);
  assert( distances->find("b")->second == -1);
  assert( distances->find("c")->second == -3);

  assert( priors->find("a")->second == "");
  assert( priors->find("b")->second == "a");
  assert( priors->find("c")->second == "b");
  
  assert ( ! nc );

  distances->clear();
  priors->clear();
  g->insertEdge("c", "a", -4);
  nc = g->BellmanFord("a", distances, priors);
  assert ( nc );
  
  
  delete distances;
  delete priors;
  delete g;










}




void discreteTest() {
  // Test on graph in Figure 3.5c of DAM v3 (Maurer)
  
  cout << "Testing Basic Insertions and Removal: \n";
  
  MatrixGraph * graph = new MatrixGraph();
  cout << "\tGraph created!" << endl;

  graph->insertVertex("a");
  graph->insertVertex("b");
  graph->insertVertex("c");

  graph->consistencyCheck();

  assert(graph->size() == 3);
  cout << "Insertions successful." << endl;

  graph->insertVertex("d");
  graph->insertVertex("e");

  graph->consistencyCheck();

  graph->insertEdge("d", "e");

  graph->consistencyCheck();

  graph->insertVertex("f");
  graph->insertEdge("d", "f", 1, "d->f");
  graph->insertEdge("e", "f", 1, "e->f");
  graph->insertEdge("f", "a", 1, "f->a");

  graph->consistencyCheck();

  cout << "\tInserted more edges!" << endl;
  // Check that removing edges and vertices works
  assert(graph->containsEdge("d", "f"));
  assert(graph->containsEdge("e", "f"));
  assert(graph->containsEdge("f", "a"));
  graph->removeEdge("d", "f");
  cout << "\tRemoving an edge!" << endl;
  // Check all proper edges are still there
  assert(graph->containsEdge("e", "f"));
  assert(graph->containsEdge("f", "a"));
  assert(graph->containsVertex("f"));
  assert(graph->containsVertex("d"));
  assert(graph->containsVertex("e"));
  assert(!graph->containsEdge("d", "f"));
  cout << "\tAll vertices still there! (pheww)" << endl;
 
  graph->removeVertex("f");
  cout << "\tRemoved a vertes!" << endl;

  assert(!graph->containsVertex("f"));
  assert(!graph->containsEdge("e", "f"));
  assert(!graph->containsEdge("f", "a"));
  assert(graph->containsVertex("a"));
  assert(graph->containsVertex("b"));
  assert(graph->containsVertex("c"));
  assert(graph->containsVertex("d"));
  assert(graph->containsVertex("e"));
  assert(graph->containsEdge("d", "e"));

  cout << "\tAll edges maintained properly!" << endl;
  cout << "\tAll vertices maintained properly!" << endl;


  /* Graph drawing:

a <<<<<<<<<<   d
  \              \
   V           |  \
   c           |    \
               V     V
               b <-> e


  */
  graph->insertEdge("a", "c", 10, "a->c");
  graph->insertEdge("d", "a", 11, "d->a");
  graph->insertEdge("d", "b", 12, "d->b");
  graph->insertEdge("e", "b", 13, "e->b");
  graph->insertEdge("b", "e", 14, "b->e");

  delete graph;
  cout << "\n***PASS***\n\n";
  return;
}


void simpleTest() {
  
  Graph * g = new MatrixGraph();
  
  g->insertEdge("a", "b", 5);
  assert(g->size() == 2);

  assert(g->containsEdge("a", "b"));
  assert(!g->containsEdge("b", "a"));
  g->removeEdge("a", "b");
  assert(g->size() == 2);
  assert(!g->containsEdge("a", "b"));
  assert(g->containsVertex("a"));
  assert(g->containsVertex("b"));
  assert(!g->containsVertex("c"));

  g->insertVertex("c");
  assert(g->containsVertex("a"));
  assert(g->containsVertex("b"));
  assert(g->containsVertex("c"));
  assert(g->size() == 3);
  g->insertEdge("b", "c");
  assert(g->size() == 3);
  g->insertEdge("c", "d");
  assert(g->size() == 4);
  g->insertEdge("d", "a");
  g->insertEdge("a", "b");

  vector < Vertex * > * neighbors = g->getNeighbors("a");
  assert(neighbors->size() == 1);
  assert(neighbors->front()->label == "b");
  delete neighbors;
  neighbors = g->getNeighbors("b");
  assert(neighbors->size() == 1);
  assert(neighbors->front()->label == "c");
  delete neighbors;
  neighbors = g->getNeighbors("c");
  assert(neighbors->size() == 1);
  assert(neighbors->front()->label == "d");
  delete neighbors;
  neighbors = g->getNeighbors("d");
  assert(neighbors->size() == 1);
  assert(neighbors->front()->label == "a");
  delete neighbors;

  vector < Edge * > * outgoing;

  outgoing = g->getOutgoingEdges("a");
  assert(outgoing->size() == 1);
  assert(outgoing->front()->dest->label == "b");
  delete outgoing;
  outgoing = g->getOutgoingEdges("b");
  assert(outgoing->size() == 1);
  assert(outgoing->front()->dest->label == "c");
  delete outgoing;
  outgoing = g->getOutgoingEdges("c");
  assert(outgoing->size() == 1);
  assert(outgoing->front()->dest->label == "d");
  delete outgoing;
  outgoing = g->getOutgoingEdges("d");
  assert(outgoing->size() == 1);
  assert(outgoing->front()->dest->label == "a");
  delete outgoing;

  vector < Edge * > * incoming;
  incoming = g->getIncomingEdges("a");
  assert(incoming->size() == 1);
  assert(incoming->front()->src->label == "d");
  delete incoming;
  incoming = g->getIncomingEdges("b");
  assert(incoming->size() == 1);
  assert(incoming->front()->src->label == "a");
  delete incoming;
  incoming = g->getIncomingEdges("c");
  assert(incoming->size() == 1);
  assert(incoming->front()->src->label == "b");
  delete incoming;
  incoming = g->getIncomingEdges("d");
  assert(incoming->size() == 1);
  assert(incoming->front()->src->label == "c");
  delete incoming;


  delete g;

}
